The present application relates generally to computing apparatus, methods and computer program products and, more particularly, to quantum computing apparatus, methods and computer program products.
Many software engineering tasks can be attacked as search problems. For example, a test generator searches for sets of inputs that result in branches or paths being covered, a finite state machine (FSM) verifier searches for inputs that lead to states where a given property is violated, and a synthesis tool searches for compositions of library components that have a specified behavior. Techniques and tools attacking software engineering problems have employed myriad search techniques, from simple exhaustive search through sophisticated heuristic searches, on sequential, parallel, and distributed platforms. While much progress has been made, and many such tools are used in practice today, these problems are NP-hard or worse and conventional tools may not solve such problems reliably. That is, while many current tools can do better than systematic brute force or random searches on some (or many) problems, they may be either heuristic or targeted at narrow sub-domains. Consequently, scaling remains a challenge in software engineering, due to the underlying problem complexity.
Quantum computing exploits the quantum mechanical phenomena of state entanglement and quantum interference to enable a very large number of computations to occur concurrently, with results discovered at the end through observation. Unfortunately, while it may be relatively straightforward to set up exponentially many quantumparallel computations, it may be much more difficult to read out the desired results reliably. As a result, with the exception of a few relatively narrow problem types, such as simulating physics and factoring an integer, it appears that the best speedup achievable is quadratic. That is, where a classical search algorithm requires n steps, there may be a quantum variant requiring only O√{square root over (N)} steps. This may be achieved using the approach discovered by L. Grover in 1996, referred to as Grover's Search (GS) Algorithm. Such a speedup could have a major impact on practice, bringing spaces much too large for today's tools (e.g. 264 states) into the reach (232 effort) of tomorrow's search tools.